#include <stdio.h>
#include <cassert>

// This class manages available ID use a single linked list, which is implemnent by an array
// We simply use an integer array to save half space as we could resue the "value" feild & the "next" feild:
// 1. The value type is of the same type of index
// 2. The value's range is the same as index
// 

const static char LIST_END = -1;

template <typename integer>
class idallocator
{
public:
	idallocator(integer _num): num(_num)
	{
		array = new integer[num];

		// Initialize the linked list. Initially, it is a full linked list with all elements linked one after another.
		head = 0;
		for (integer i = 0; i < num; i++)
		{
			array[i] = i + 1;
		}
		array[num-1] = LIST_END;

		count = num;
	}

	~idallocator()
	{
		delete [] array;
	}



	integer allocate() // pop_front, remove a node from the front
	{
		int id = head;
		if(id != LIST_END)
		{
			head = array[head];
			count--;
		}
		return id;
	}

	// push_front, add a new node to the front
	void free(const integer& id) 
	{
		array[id] = head;
		count++;
		head = id;
	}

	// push_front, add a new node to the front
	bool free_s(const integer& id) 
	{
		// make sure this id is not in the list before we add it
		if(exist(id)) return false; 
		free(id);
		return true;
	}

	size_t size() const
	{
		return count;
	}

private:
	bool exist(const integer& id)
	{
		int i = head;
		while (i != LIST_END)
		{
			if(i == id) return true;
			i = array[i];
		}

		return false;
	}

private:
	integer* array;
	integer num;		// totall number of the array
	integer count;		// number in the linked list
	int head;		// index of the head of the linked list

};


int main()
{
	//idallocator<unsigned char> idor(12);
	//idallocator<unsigned int> idor(12);
	//idallocator<int> idor(12);
	idallocator<long> idor(12);
	printf("idallocator<xxx> idor(12)\n");
	printf("size = %d\n", idor.size());
	printf("allocated = %d\n", idor.allocate());
	printf("allocated = %d\n", idor.allocate());
	printf("allocated = %d\n", idor.allocate());

	int id = idor.allocate();
	printf("allocated = %d\n", id);
	printf("size = %d\n", idor.size());

	idor.free(id);
	printf("size = %d\n", idor.size());

	printf("allocated = %d\n", idor.allocate());


	return 0;
}

